1965. Шеренга

 

Петя Васечкин перевёлся в другую школу. На первом уроке физкультуры ему нужно было определить своё место в строю.

 

Вход. В первой строке задано число n  количество учеников в классе.

Во второй строке дана невозрастающая последовательность из n натуральных чисел, описывающая рост каждого ученика в строю.

В третьей строке указано число x рост Пети.

Все числа натуральные и не превышают 200.

 

Выход. Выведите номер позиции, на которую должен встать Петя.

Если в строю уже есть ученики с таким же ростом, как у Пети, он должен встать сразу после них.

 

Пример входа 1

Пример выхода 1

8
165 163 160 160 157 157 155 154 

162

3

 

 

Пример входа 2

Пример выхода 2

8
165 163 160 160 157 157 155 154 
160

5

 

 

РЕШЕНИЕ

бинарный поиск

 

Анализ алгоритма

Входная последовательность уже отсортирована в невозрастающем порядке. Найдём позицию Пети с помощью бинарного поиска по верхней границе. Нумерация позиций в строю начинается с 1.

 

Реализация алгоритма

Читаем входные данные. Заносим рост школьников в массив v.

 

scanf("%d",&n);

v.resize(n);

for(i = 0; i < n; i++)

  scanf("%d",&v[i]);

scanf("%d",&x);

 

Если в строю есть школьники с ростом, равным росту Пети, он становится после них. Для поиска позиции Пети используем бинарный поиск по верхней границе это возможно, поскольку массив отсортирован в невозрастающем порядке.

 

pos = upper_bound(v.begin(),v.end(),x,greater<int>()) - v.begin();

 

Выводим позицию Пети, учитывая, что в задаче нумерация школьников начинается с единицы.

 

printf("%d\n",pos + 1);

 

Реализация алгоритма – собственный бинарный поиск

Читаем входные данные. Заносим рост школьников в массив v.

 

scanf("%d",&n);

v.resize(n+1);

for(i = 1; i <= n; i++)

  scanf("%d",&v[i]);

scanf("%d",&x);

 

Петя может занять любую позицию от 1 до n + 1. Инициализируем интервал бинарного поиска: [Left; Right] = [1; n + 1].

 

int Left = 1, Right = n + 1, Middle;

 

Запускаем бинарный поиск.

 

while(Left < Right)

{

  Middle = (Left + Right) / 2;

  if (x <= v[Middle]) Left = Middle + 1; else Right = Middle;

}

 

Выводим ответ – позицию Пети в строю.

 

printf("%d\n",Left);